package com.hqq.search;

import com.hqq.search.KeyMap;

import java.util.Iterator;

/**
 * OrderedKeyMap
 * 键有序的符号表
 * Created by heqianqian on 2017/8/5.
 */
public interface OrderedKeyMap<K extends Comparable<K>, V> extends KeyMap<K, V> {

    @Override
    default Iterator<K> iterator() {
        return iterator(min(), max());
    }

    /**
     * 迭代low-high之间所有的key
     */
    Iterator<K> iterator(K low, K high);

    K max();

    K min();

    int rank(K key);

    /**
     * 排名为k的键
     */
    K select(int k);

    default void deleteMin() {
        delete(min());
    }

    default void deleteMax() {
        delete(max());
    }

    /**
     * 返回low-high之间值的数量
     */
    default int size(K low, K high) {
        if (high.compareTo(low) < 0) {
            return 0;
        } else if (contains(high)) {
            return rank(high) - rank(low) + 1;
        } else {
            return rank(high) - rank(low);
        }
    }

}
